#pragma once
#include <iostream>
#include <map>
#include <vector>
#include <queue>
#include <functional>
#include <climits>
#include <cassert>
#include <cstring>
#include "unionFindSet.h"
namespace matrix_graph
{
    // V：顶点的类型  W：边的权值的类型
    // MAX_W：最大权值  Direction：是否为有向图 （后两个是非类型模版参数）
    template <class V, class W, W MAX_W = INT_MAX, bool Direction = false>
    class Graph
    {
    public:
        typedef Graph<V, W, MAX_W, Direction> Self;

    private:
        std::vector<V> _vertexs;             // 保存顶点
        std::vector<std::vector<W>> _matrix; // 邻接矩阵
    private:
        std::map<V, int> _vIndex; // 根据顶点快速找在数组中的索引
    public:
        Graph() = default;
        // 构造图：先传入顶点，顶点间的关系调用函数AddEdge添加
        Graph(const V *vertexs, size_t n)
        {
            _vertexs.reserve(n);
            for (size_t i = 0; i < n; ++i)
            {
                _vertexs.push_back(vertexs[i]);
                _vIndex[vertexs[i]] = i;
            }
            // MAX_W 作为不存在边的标识值
            _matrix.resize(n);
            for (auto &e : _matrix)
                e.resize(n, MAX_W);
        }

    private:
        void _AddEdge(size_t srci, size_t dsti, const W &w)
        {
            _matrix[srci][dsti] = w;
            if (Direction == false)
                _matrix[dsti][srci] = w;
        }

    public:
        // 添加边
        void AddEdge(const V &src, const V &dst, const W &w)
        {
            size_t srci = _GetVertexIndex(src);
            size_t dsti = _GetVertexIndex(dst);
            _AddEdge(srci, dsti, w);
        }
        void Print()
        {
            using std::cout;
            using std::endl;

            // 打印顶点和下标映射关系
            for (size_t i = 0; i < _vertexs.size(); ++i)
                cout << _vertexs[i] << "-" << i << " ";
            cout << endl
                 << endl;
            cout << "  ";
            for (size_t i = 0; i < _vertexs.size(); ++i)
                cout << i << " ";
            cout << endl;
            // 打印矩阵
            for (size_t i = 0; i < _matrix.size(); ++i)
            {
                cout << i << " ";
                for (size_t j = 0; j < _matrix[i].size(); ++j)
                    if (_matrix[i][j] != MAX_W)
                        cout << _matrix[i][j] << " ";
                    else
                        cout << "#"
                             << " ";
                cout << endl;
            }
        }
        // 广度优先遍历
        void BFS(const V &src)
        {
            using namespace std;
            int srci = _GetVertexIndex(src);
            vector<bool> visited(_vertexs.size(), false);
            queue<int> q;

            q.push(srci);
            visited[srci] = true;
            size_t n = _vertexs.size();
            while (!q.empty())
            {
                int levelSize = q.size();
                for (int i = 0; i < levelSize; ++i)
                {
                    int front = q.front();
                    q.pop();
                    cout << front << ":" << _vertexs[front] << " ";
                    for (size_t i = 0; i < n; ++i)
                        if (_matrix[front][i] != MAX_W && visited[i] == false)
                        {
                            q.push(i);
                            visited[i] = true;
                        }
                }
                cout << endl;
            }

            cout << endl;
        }

    private:
        void _DFS(size_t srci, std::vector<bool> &visited)
        {
            std::cout << srci << ":" << _vertexs[srci] << std::endl;
            visited[srci] = true;

            for (size_t i = 0; i < _vertexs.size(); ++i)
                if (_matrix[srci][i] != MAX_W && visited[i] == false)
                    _DFS(i, visited);
        }

    public:
        void DFS(const V &src)
        {
            size_t srci = _GetVertexIndex(src);
            std::vector<bool> visited(_vertexs.size(), false);

            _DFS(srci, visited);
        }
        struct Edge
        {
            size_t _srci;
            size_t _dsti;
            W _w;
            Edge(size_t srci, size_t dsti, const W &w)
                : _srci(srci), _dsti(dsti), _w(w)
            {
            }
            bool operator>(const Edge &e) const
            {
                return _w > e._w;
            }
        };
        // 获取当前图的最小生成树，并以参数形式保存到minTree中
        // minTree传入一个空图（无参构造）即可。
        // 返回总权值
        W Kruskal(Self &minTree)
        {
            using namespace std;
            size_t n = _vertexs.size();
            /// 1.为minTree初始化空间
            minTree._vertexs = _vertexs;
            minTree._vIndex = _vIndex;
            minTree._matrix.resize(n);
            for (size_t i = 0; i < n; ++i)
                minTree._matrix[i].resize(n, MAX_W);
            /// 2.用小根堆保存当前图的边的信息，以边的边权为比较逻辑。
            priority_queue<Edge, vector<Edge>, greater<Edge>> minque;
            for (size_t i = 0; i < n; ++i)
                for (size_t j = 0; j < n; ++j)
                    if (i < j) // 当前是无向图，排除掉矩阵中另一半重复的根信息。
                        if (_matrix[i][j] != MAX_W)
                            minque.push(Edge(i, j, _matrix[i][j]));
            /// 3.给minTree添加边权最小的边，用并查集排除成环的边
            int size = 0;
            W totalW = W();
            UnionFindSet ufs(n);
            while (!minque.empty())
            {
                Edge min = minque.top();
                minque.pop();

                if (!ufs.InSet(min._srci, min._dsti))
                {
                    cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
                    minTree._AddEdge(min._srci, min._dsti, min._w);
                    ufs.Union(min._srci, min._dsti);
                    ++size;
                    totalW += min._w;
                }
                else
                {
                    cout << "成环：";
                    cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
                }
            }

            if (size == n - 1)
                return totalW;
            else
                return W();
        }

    private:
        // 获取顶点对应于数组的下标
        size_t _GetVertexIndex(const V &v)
        {
            auto ret = _vIndex.find(v);
            if (ret != _vIndex.end())
            {
                return ret->second;
            }
            else
            {
                assert(false);
                return -1;
            }
        }
    };
    void TestGraphMinTree()
    {
        using namespace std;
        const char *str = "abcdefghi";
        Graph<char, int> g(str, strlen(str));
        g.AddEdge('a', 'b', 4);
        g.AddEdge('a', 'h', 8);
        // g.AddEdge('a', 'h', 9);
        g.AddEdge('b', 'c', 8);
        g.AddEdge('b', 'h', 11);
        g.AddEdge('c', 'i', 2);
        g.AddEdge('c', 'f', 4);
        g.AddEdge('c', 'd', 7);
        g.AddEdge('d', 'f', 14);
        g.AddEdge('d', 'e', 9);
        g.AddEdge('e', 'f', 10);
        g.AddEdge('f', 'g', 2);
        g.AddEdge('g', 'h', 1);
        g.AddEdge('g', 'i', 6);
        g.AddEdge('h', 'i', 7);

        Graph<char, int> kminTree;
        cout << "Kruskal:" << g.Kruskal(kminTree) << endl;
        kminTree.Print();
    }

    void TestGraph()
    {
        Graph<char, int, INT_MAX, true> g("abcd", 4);
        g.AddEdge('a', 'b', 1);
        g.AddEdge('a', 'd', 4);
        g.AddEdge('b', 'd', 2);
        g.AddEdge('b', 'c', 9);
        g.AddEdge('c', 'd', 8);
        g.AddEdge('c', 'b', 5);
        g.AddEdge('c', 'a', 3);
        g.AddEdge('d', 'c', 6);
        g.Print();
    }
    void TestBFS_DFS()
    {
        Graph<char, int, INT_MAX, true> g("abcd", 4);
        g.AddEdge('a', 'b', 1);
        g.AddEdge('a', 'd', 4);
        g.AddEdge('b', 'd', 2);
        g.AddEdge('b', 'c', 9);
        g.AddEdge('c', 'd', 8);
        g.AddEdge('c', 'b', 5);
        g.AddEdge('c', 'a', 3);
        g.AddEdge('d', 'c', 6);
        g.BFS('a');
        g.DFS('a');
    }
}

namespace linkTable_graph
{
    template <class W>
    struct Edge
    {
        // int _srci;
        int _dsti; //
        W _w;      //
        Edge<W> *_next;

        Edge(int dsti, const W &w)
            : _dsti(dsti), _w(w), _next(nullptr)
        {
        }
    };

    template <class V, class W, bool Direction = false>
    class Graph
    {
    public:
        typedef struct Edge<W> Edge;

    private:
        std::vector<V> _vertexs;    // 保存顶点
        std::vector<Edge *> _table; // 邻接表
    private:
        std::map<V, int> _vIndex; // 根据顶点快速找在数组中的索引
    public:
        Graph(const V *a, size_t n)
        {
            _vertexs.reserve(n);
            for (size_t i = 0; i < n; ++i)
            {
                _vertexs.push_back(a[i]);
                _vIndex[a[i]] = i;
            }

            _table.resize(n, nullptr);
        }
        void AddEdge(const V &src, const V &dst, const W &w)
        {
            size_t srci = GetVertexIndex(src);
            size_t dsti = GetVertexIndex(dst);

            // 1->2
            Edge *eg = new Edge(dsti, w);
            eg->_next = _table[srci];
            _table[srci] = eg;

            // 2->1
            if (Direction == false)
            {
                Edge *eg = new Edge(srci, w);
                eg->_next = _table[dsti];
                _table[dsti] = eg;
            }
        }
        void Print()
        {
            using std::cout;
            using std::endl;
            for (size_t i = 0; i < _vertexs.size(); ++i)
            {
                cout << "[" << i << "]"
                     << "->" << _vertexs[i] << endl;
            }
            cout << endl;

            for (size_t i = 0; i < _table.size(); ++i)
            {
                cout << _vertexs[i] << "[" << i << "]->";
                Edge *cur = _table[i];
                while (cur)
                {
                    cout << "[" << _vertexs[cur->_dsti] << ":" << cur->_dsti << ":" << cur->_w << "]->";
                    cur = cur->_next;
                }
                cout << "nullptr" << endl;
            }
        }

    private:
        size_t GetVertexIndex(const V &v)
        {
            auto it = _vIndex.find(v);
            if (it != _vIndex.end())
            {
                return it->second;
            }
            else
            {
                assert(false);
                return -1;
            }
        }
    };
    void TestGraph()
    {
        std::string a[] = {"张三", "李四", "王五", "赵六"};
        Graph<std::string, int, true> g1(a, 4);
        g1.AddEdge("张三", "李四", 100);
        g1.AddEdge("李四", "王五", 200);
        g1.AddEdge("张三", "赵六", 30);
        g1.Print();
    }
}